//有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。 
//
// 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上
//单元格 高于海平面的高度 。 
//
// 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。 
//
// 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可
//流向大西洋 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
//输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
// 
//
// 示例 2： 
//
// 
//输入: heights = [[2,1],[1,2]]
//输出: [[0,0],[0,1],[1,0],[1,1]]
// 
//
// 
//
// 提示： 
//
// 
// m == heights.length 
// n == heights[r].length 
// 1 <= m, n <= 200 
// 0 <= heights[r][c] <= 10⁵ 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 数组 矩阵 👍 778 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @author ldltd
 * @date 2025-10-05 19:48:58
 * @description 417.太平洋大西洋水流问题
 */
public class PacificAtlanticWaterFlow{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PacificAtlanticWaterFlow fun=new PacificAtlanticWaterFlow();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	int[] dx = new int[]{-1, 0, 1, 0}; // 上右下左
	int[] dy = new int[]{0, 1, 0, -1};

	public List<List<Integer>> pacificAtlantic1(int[][] heights) {
		int m = heights.length;
		int n = heights[0].length;

		int[][] vis = new int[m][n];

		// 初始化边界
		for (int i = 0; i < m; i++) {
			vis[i][0] |= 1;  // 左边界-太平洋
			vis[i][n - 1] |= 2; // 右边界-大西洋
		}
		for (int j = 0; j < n; j++) {
			vis[0][j] |= 1;  // 上边界-太平洋
			vis[m - 1][j] |= 2; // 下边界-大西洋
		}

		// 使用BFS思想进行多轮传播
		boolean changed;
		do {
			changed = false;
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					// 从边界往高处蔓延
					if (vis[i][j] == 0) continue;

					// 检查四个方向，传播标记
					for (int k = 0; k < 4; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];

						if (nx >= 0 && nx < heights.length && ny >= 0 && ny < heights[0].length
								&& heights[nx][ny] >= heights[i][j]) {
							// 如果邻居可以获得新的标记
							if ((vis[nx][ny] | vis[i][j]) != vis[nx][ny]) {
								vis[nx][ny] |= vis[i][j];
								changed = true;
							}
						}
					}
				}
			}
		} while (changed);

		// 收集结果
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (vis[i][j] == 3) {
					ans.add(List.of(i, j));
				}
			}
		}
		return ans;
	}


	public List<List<Integer>> pacificAtlantic(int[][] heights) {
		int m = heights.length;
		int n = heights[0].length;

		// 初始化访问标记数组
		int[][] vis = new int[m][n];

		// 标记太平洋边界（左边界和上边界）
		for (int i = 0; i < m; i++) {
			dfs(heights, vis, i, 0, 1); // 1表示太平洋
		}
		for (int j = 0; j < n; j++) {
			dfs(heights, vis, 0, j, 1); // 1表示太平洋
		}

		// 标记大西洋边界（右边界和下边界）
		for (int i = 0; i < m; i++) {
			dfs(heights, vis, i, n - 1, 2); // 2表示大西洋
		}
		for (int j = 0; j < n; j++) {
			dfs(heights, vis, m - 1, j, 2); // 2表示大西洋
		}
		/*
		 // BFS标记太平洋
			Queue<int[]> queue = new LinkedList<>();
			for (int i = 0; i < m; i++) {
				vis[i][0] |= 1;
				queue.offer(new int[]{i, 0});
			}
			for (int j = 0; j < n; j++) {
				vis[0][j] |= 1;
				queue.offer(new int[]{0, j});
			}
			bfs(heights, vis, queue, 1);

			// BFS标记大西洋
			queue = new LinkedList<>();
			for (int i = 0; i < m; i++) {
				vis[i][n - 1] |= 2;
				queue.offer(new int[]{i, n - 1});
			}
			for (int j = 0; j < n; j++) {
				vis[m - 1][j] |= 2;
				queue.offer(new int[]{m - 1, j});
			}
			bfs(heights, vis, queue, 2);
			* */
		// 收集结果
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (vis[i][j] == 3) { // 3 = 1 | 2，表示可以流向两个海洋
					ans.add(List.of(i, j));
				}
			}
		}
		return ans;
	}

	private void dfs(int[][] heights, int[][] vis, int i, int j, int ocean) {
		// 如果这个单元格已经被当前海洋标记过，直接返回（避免重复访问）
		if ((vis[i][j] & ocean) != 0) {
			return;
		}

		// 标记当前单元格
		vis[i][j] |= ocean;

		// 向四个方向DFS
		for (int k = 0; k < 4; k++) {
			int nx = i + dx[k];
			int ny = j + dy[k];

			// 检查边界条件，并且下一个单元格的高度 >= 当前单元格高度
			if (nx >= 0 && nx < heights.length && ny >= 0 && ny < heights[0].length
					&& heights[nx][ny] >= heights[i][j]) {
				dfs(heights, vis, nx, ny, ocean);
			}
		}
	}
	private void bfs(int[][] heights, int[][] vis, Queue<int[]> queue, int ocean) {
		while (!queue.isEmpty()) {
			int[] cell = queue.poll();
			int i = cell[0], j = cell[1];

			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];

				if (nx >= 0 && nx < heights.length && ny >= 0 && ny < heights[0].length
						&& heights[nx][ny] >= heights[i][j] && (vis[nx][ny] & ocean) == 0) {
					vis[nx][ny] |= ocean;
					queue.offer(new int[]{nx, ny});
				}
			}
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
